package leetcode.D400.T354;

import java.util.Arrays;

/**
 * @Author: 18362
 * @Create: 2022-09-19 23:51:24 星期一
 */
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (a, b) -> {
            if (a[0] != b[0])
                return a[0] - b[0];
            return b[1] - a[1];
        });
        int[] low = new int[envelopes.length];
        low[0] = envelopes[0][1];
        int k = 1;
        for (int i = 0; i < envelopes.length; i++) {
            if (envelopes[i][1] > low[k-1])
                low[k++] = envelopes[i][1];
            else {
                int idx = lowerBound(low, k, envelopes[i][1]);
                low[idx] = envelopes[i][1];
            }
        }
        return k;
    }

    private int lowerBound(int[] nums, int len, int target) {
        int left = 0, right = len-1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target)
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }
}
